package com.sfx.算法专题.动态规划.完全背包;

import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description: 完全背包模板题
 * User: sfx
 * Date: 2023-07-16
 * Time: 16:06
 */
public class Code_1_knapsack {

    //一维dp
    static class Solution1 {
        public int f1(int weight, int n, int[] v, int[] w) {
            //从前i个物品中选择,总体积不超过j的最大价值为dp[i][j]
            int[] dp = new int[weight + 1];
            //状态转移方程为 :
            // dp[i][j] = Math.max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
            // 以最后一个i号物品来划分问题,到底选不选第i号物品
            // 不选 : dp[i-1][j]
            // 选1个: dp[i-1][j-v[i]] + w[i]
            // 选2个: dp[i-1][j-2*v[i]] + 2*w[i]
            // 选3个: dp[i-1][j-3*v[i]] + 3*w[i]
            // 在选择i号物品的状态转移为 :
            //dp[i][j] = dp[i-1][j-v[i]] + w[i],dp[i-1][j-2*v[i]] + 2*w[i],dp[i-1][j-3*v[i]] + 3*w[i]...求一个最大值
            //可以根据规律他们都减去v[i]
            //dp[i][j-v[i]] = dp[i-1][j-2*v[i]],dp[i-1][j-3*v[i]]+2w[i],dp[i-1][j-4*v[i]] + 3w[i]
            //当我们加上w[i]就和后面的相等了
            //dp[i][j-v[i]] + w[i] = dp[i-1][j-v[i]] + w[i],dp[i-1][j-2*v[i]] + 2*w[i],dp[i-1][j-3*v[i]] + 3*w[i]
            //所以就可以利用dp[i][j-v[i]] + w[i]替换上面一大堆
            //综上 : dp[i][j] = Math.max(dp[i-1][j],dp[i][j-v[i] + w[i]);
            for (int i = 1; i <= n; ++i) {
                for (int j = v[i]; j <= weight; ++j) {
                    dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
                }
            }
            return dp[weight];
        }

        public int f2(int weight, int n, int[] v, int[] w) {
            //从前i个物品中选择,总体积一定为j的最大价值为dp[i][j]
            int[] dp = new int[weight + 1];
            //状态转移方程为 :
            // dp[i][j] = Math.max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
            dp[0] = 0;
            for (int j = 1; j <= weight; ++j) {
                dp[j] = -0x3f3f3f3f;
            }
            for (int i = 1; i <= n; ++i) {
                for (int j = v[i]; j <= weight; ++j) {
                    dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
                }
            }
            return Math.max(dp[weight], 0);
        }

        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * @param weight int整型 最多能容纳的体积是V。
         * @param n      int整型 最多能容纳的体积是V。
         * @param nums   int整型ArrayList<ArrayList<>>  第i种物品的体积为vi,价值为wi
         * @return int整型ArrayList
         */
        public ArrayList<Integer> knapsack(int weight, int n, ArrayList<ArrayList<Integer>> nums) {
            int[] v = new int[n + 1];//体积
            int[] w = new int[n + 1];//价值
            int i = 1;
            int j = 1;
            for (ArrayList<Integer> array : nums) {
                v[i++] = array.get(0);//体积
                w[j++] = array.get(1);//价值
            }
            ArrayList<Integer> res = new ArrayList<>();
            int maxValue1 = f1(weight, n, v, w);
            res.add(maxValue1);
            int maxValue2 = f2(weight, n, v, w);
            res.add(maxValue2);
            return res;
        }
    }

    //二维dp
    static class Solution2 {
        public int f1(int weight,int n,int[] v,int[] w) {
            //从前i个物品中选择,总体积不超过j的最大价值为dp[i][j]
            int[][] dp = new int[n+1][weight+1];
            //状态转移方程为 :
            // dp[i][j] = Math.max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
            // 以最后一个i号物品来划分问题,到底选不选第i号物品
            // 不选 : dp[i-1][j]
            // 选1个: dp[i-1][j-v[i]] + w[i]
            // 选2个: dp[i-1][j-2*v[i]] + 2*w[i]
            // 选3个: dp[i-1][j-3*v[i]] + 3*w[i]
            // 在选择i号物品的状态转移为 :
            //dp[i][j] = dp[i-1][j-v[i]] + w[i],dp[i-1][j-2*v[i]] + 2*w[i],dp[i-1][j-3*v[i]] + 3*w[i]...求一个最大值
            //可以根据规律他们都减去v[i]
            //dp[i][j-v[i]] = dp[i-1][j-2*v[i]],dp[i-1][j-3*v[i]]+2w[i],dp[i-1][j-4*v[i]] + 3w[i]
            //当我们加上w[i]就和后面的相等了
            //dp[i][j-v[i]] + w[i] = dp[i-1][j-v[i]] + w[i],dp[i-1][j-2*v[i]] + 2*w[i],dp[i-1][j-3*v[i]] + 3*w[i]
            //所以就可以利用dp[i][j-v[i]] + w[i]替换上面一大堆
            //综上 : dp[i][j] = Math.max(dp[i-1][j],dp[i][j-v[i] + w[i]);

            for(int i =1;i<=n;++i) {
                for(int j = 0;j<=weight;++j) {
                    dp[i][j] = dp[i-1][j];
                    if(j>=v[i]) {
                        dp[i][j] = Math.max(dp[i][j],dp[i][j-v[i]]+w[i]);
                    }
                }
            }
            return dp[n][weight];
        }

        public int f2(int weight,int n,int[] v,int[] w) {
            //从前i个物品中选择,总体积一定为j的最大价值为dp[i][j]
            int[][] dp = new int[n+1][weight+1];
            //状态转移方程为 :
            // dp[i][j] = Math.max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
            dp[0][0] = 0;
            for(int j=1;j<=weight;++j) {
                dp[0][j] = -1;
            }
            for(int i =1;i<=n;++i) {
                for(int j = 0;j<=weight;++j) {
                    dp[i][j] = dp[i-1][j];
                    if(j>=v[i]&&dp[i][j-v[i]]!= -1) {
                        dp[i][j] = Math.max(dp[i][j],dp[i][j-v[i]]+w[i]);
                    }
                }
            }
            return dp[n][weight] == -1 ? 0 : dp[n][weight];
        }
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         * @param weight int整型 最多能容纳的体积是V。
         * @param n int整型 最多能容纳的体积是V。
         * @param nums int整型ArrayList<ArrayList<>>  第i种物品的体积为vi,价值为wi
         * @return int整型ArrayList
         */
        public ArrayList<Integer> knapsack (int weight, int n, ArrayList<ArrayList<Integer>> nums) {
            int[] v = new int[n+1];//体积
            int[] w = new int[n+1];//价值
            int i = 1;
            int j = 1;
            for(ArrayList<Integer> array : nums) {
                v[i++] = array.get(0);//体积
                w[j++] = array.get(1);//价值
            }
            ArrayList<Integer> res = new ArrayList<>();
            int maxValue1 = f1(weight,n,v,w);
            res.add(maxValue1);
            int maxValue2 = f2(weight,n,v,w);
            res.add(maxValue2);
            return res;
        }
    }

}